package interview.huawei.tjt.training.dongtaiguihua;

import java.util.ArrayList;
import java.util.List;

/**
 * 多重背包：
 * 有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
 *
 * 多重背包和01背包是非常像的， 为什么和01背包像呢？
 *
 * 每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
 *
 * 例如：
 *
 * 背包最大重量为10。
 *
 * 物品为：
 *
 * 重量	价值	数量
 * 物品0	1	15	2
 * 物品1	3	20	3
 * 物品2	4	30	2
 * 问背包能背的物品最大价值是多少？
 *
 * 和如下情况有区别么？
 *
 * 重量	价值	数量
 * 物品0	1	15	1
 * 物品0	1	15	1
 * 物品1	3	20	1
 * 物品1	3	20	1
 * 物品1	3	20	1
 * 物品2	4	30	1
 * 物品2	4	30	1
 * 毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
 */
public class BagOfMulti {

    public static void main(String[] args) {
        List<Integer> weight = new ArrayList<>();
        weight.add(1);
        weight.add(3);
        weight.add(4);
        List<Integer> value = new ArrayList<>();
        value.add(15);
        value.add(20);
        value.add(30);
        List<Integer> nums = new ArrayList<>();
        nums.add(2);
        nums.add(3);
        nums.add(2);
        int bagWeight = 10;
        for (int i = 0; i < nums.size(); i ++) {
            int num = nums.get(i);
            while (num > 1) {
                weight.add(weight.get(i));
                value.add(value.get(i));
                num --;
            }
        }

        int[] dp = new int[bagWeight + 1];
        dp[0] = 0;
        for (int i = 0; i < weight.size(); i ++) {
            // 从后往前遍历确保每个物品只使用一次
            for (int j = bagWeight; j >= weight.get(i); j --) {
                dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
            }
        }
        for (int i = 0; i < dp.length; i ++) {
            System.out.print(dp[i] + " ");
        }
    }

}
